package n2229;

import java.util.Scanner;

public class Main {

	static int base[]=new int[1000001];
	
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {

		
		Scanner cin=new Scanner(System.in);
		
		int num=cin.nextInt();
		base[0]=0;
		base[1]=1;
		base[2]=2;
		boolean flag=false;
		for(int i=3;i<=num;i++)
		{
			if((i&1)==0){
				base[i]=base[i-1]+base[i>>1];
				if(base[i]>=1000000000){
					flag=true;
					base[i]-=1000000000;
				}
			}else{
				base[i]=base[i-1];
			}
		}
//		if(flag)
//		{
//			int tmp=base[num];
//			int digits=0;
//			while(tmp>0)
//			{
//				digits++;
//				tmp=tmp/10;
//			}
//			for(int i=0;i<9-digits;i++)System.out.print("0");
//			System.out.println(base[num]);
//		}else
//		{
			System.out.println(base[num]);
//		}

	}

}
